A method to determine an object contour, referred to as minimal path, between two fixed end points in a 2-D image, is disclosed in the publication “Global Minimum for Active Contour Models: A minimal Path Approach” by Laurent D. COHEN and Ron KIMMEL, in International Journal of Computer Vision 24(1), 57–78 (1997). This method proposes a technique of boundary detection of objects for shape modeling in 2-D images. This method particularly aims at solving the boundary detection problem by mapping it into a global minimum problem and by determining a path of minimal length from the solution of that global minimum problem. The method guarantees that a global minimum of energy is found by minimizing curves between two end points. This method implements a step of (1) manually selecting a start point and an end point in an object contour region of a gradient image, (2) a step of propagating a front, in the totality of the gradient image, starting at the start point, in such manner that this front propagates at lower cost in regions of high gradient values until the end point is reached to thereby determine a cost map that is a totally convex surface having a single minimum and (3) a step of back-propagating from the end point towards the start point by the steepest gradient descent in the totally convex surface to thereby provide a minimal path between the start and end points.
This publication includes by reference a front propagation technique disclosed in a publication entitled “A fast marching level set method for monotonically advancing fronts” by J. A. SETHIAN in Proc. Nat. Acad. Sci., USA, Vol. 93, pp. 1591–1595, February 1996, Applied Mathematics. According to the reference, a front, formed in a 2-D grid of potential values, is propagated using a “Fast Marching Technique” with a determination of the front points. The front is a solution of a so-called Eikonal Equation. The Fast Marching Technique introduces order in the selection of the grid points and sweeps the front ahead in one pass on the 2-D image. The Fast Marching Technique implements a marching of the Front outwards by freezing already visited points denoted Alive, coming from a set of points referred to as Narrow Band, and by bringing new ones denoted Far Away into the Narrow Band. The Narrow Band grid points are always updated as those having minimal potential values in a neighboring structure denoted Min-Heap and the potential of the neighbors are further re-adjusted.
The method known from COHEN's publication constructs the convex surface of the cost map using the Fast Marching technique, which provides respectively one path of minimal cost joining the start point to each respective point of the front, said the front propagating until the end point is reached. Then, the minimal path is provided by back-propagating from the end point to the start point by the steepest gradient descent in the convex surface. The numerous paths constructed by propagating the front forwards and joining the start point to the different points of the front for forming the convex surface are no longer taken into account. Even the path joining the start point to the end point, in the operation of forwarding the front, is not the steepest gradient descent in the back-propagation operation.
So, the final path obtained by this known method does not have points extracted by tracking. Neither does it have points of a path constructed by front propagation.
Besides, it is interesting to note that the points of a path constructed in the operation of marching the front forwards are points which have the smallest possible potentials. Starting at the start point, and going forwards from one point to the next point must be at the “minimal cost”. So, such a path is a path of “minimal Action”, i.e. a path on which the “Sum” or the “Integral” of potentials calculated over point potentials is the smallest, though strictly continuously growing as a function of the number of points present on the path between the start point and the current point on the front.
A first problem in extracting a threadlike structure is that the threadlike structure may be represented in the original image by a number of thin linear segments which are not joined in a strictly continuous manner, having “holes” between them and which are to be found among a great number of other thin unrelated structures, referred to as false alarms. A second problem is that the threadlike structure may be very long and sinuous, so that it may be far from a straight line and may even present U-turns along its length, and that it may be formed by a great number of points.
On the one hand, a path constructed using the front propagation technique described in the known publication is not adapted to solve these problems, due to the fact that the front propagation is based on an “Action”, i.e. a “Sum” of potentials effectuated along the constructed path. Because the threadlike structure is very long, this Sum of potentials will soon become very large on a path following the threadlike structure. When the Sum becomes large, the cost becomes high, and, for minimizing costs, the known front marching technique may generate a path based on the nearest false alarms in order to follow as few points as possible. So, the known front marching technique may generate a path which is far from following the sinuous and long threadlike structure.
On the other hand, the minimal path obtained by the above described minimal path method is a smoothed path, which may not possibly provide extracted points strictly following a long and sinuous threadlike structure.